ECE 6605 - Information Theory

Prof. Matthieu Bloch

Tuesday September 19, 2023

Announcements

Assignment 2
- Posted on Canvas/Gradescope on Monday, September 18, 2023
- Due on Thursday September 28, 2023
- 6 problems on chain rules, typicality
- Read Chapter 4 of Thomas M. Cover and Joy A. Thomas, Elements of Information Theory
Last time
- Typicality
- Introduction to source coding
Today
- Converse for source coding
- Random binning for achievability proof
- Oone-shot result, smoothing
- (A cool new result: Source coding with side information, time permitting)

Fixed-length source coding

A fixed-lenght $(n,M_n)$ code for a discrete memoryless source $p_X$ consists of:

A encoding function $f_n:\calX^n\to\set{1;M_n}$
A decoding function $g_n:\set{1;M_n}\to \calX^n$

The performance of an $(n,M_n)$ code is measured in terms of
1. The rate of the code $R\eqdef \frac{\log_2 M_n}{n}$ (bits/source symbol)
2. The average probability of error
  
  \[\begin{align*} P_e^{(n)}(\calC) \eqdef \P{\widehat{X}^n\neq X^n} \eqdef \sum_{x^n\in\calX^n}P_X^{\otimes n}(x^n)\indic{g_n(f_n(x^n))\neq x^n}. \end{align*}\]

Fixed length source coding

Question 1: for a fixed $n\in\bbN$, what is the minimum $R$ required to achieve $P_e^{(n)}\leq \epsilon$?
Question 2: as $n\to\infty$, what is the minimum $R$ that ensures that $\lim_{n\to \infty} P_e^{(n)}=0$ \[ C_{\textsf{source}}\eqdef \inf\left\{R: \exists {(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0\right\} \]

For a discrete memoryless source $p_X$, $C_{\textsf{source}} = \bbH(X)$

This is an asymptotic results as $n\to\infty$ without any consideration of the complexity of decoding
One can get rates as close to the entropy as one wishes as long as $n$ is large enough (achievability)
One cannot compress below the entropy (converse)

Converse

Consider a sequence of fixed length $(n,M_n)$ source codes $\set{(f_n,g_n)}_{n\geq1}$ such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \] Then $R\geq \bbH(X)$.

Achievability - One Shot Lemma

The achievability follows using a technique called random binning
Consider a source $P_U$ assume $\textsf{supp}(U) = \calU$, and set $n=1$ for simplicity

Define the set \[ \calB_\gamma\eqdef\left\{u\in\calU:\log\frac{1}{P_{U}(u)}\leq\gamma\right\}. \]
Encoding function $f:\calU\to \set{1;M}$ created by assigning an index uniformly at random in $\set{1;M}$ to each $u\in\calU$
Decoding function $g:\intseq{1}{M}:m\mapsto u^*$, where $u^*=u$ if $u$ is the unique sequence such that $u\in\calB_\gamma$ and $f(u)=w$; otherwise, a random $u$ is declared

On average (over the random binning to create $F$), \[ \E[C]{P_e} \leq \P[P_{U}]{U\notin \calB_\gamma} + \frac{2^{\min(\gamma,\log_2\abs{\calU})}}{M}. \]

Achievability - Specializing one shot lemma

Approach 1: worst case analysis for $\E{P_e}\leq \epsilon$
- Choose $\gamma \eqdef -\log_2\min_{u\in{\calU}}p_U(u)$
\[ \log M = \log_2\card{\calU} + \log_2\frac{1}{\epsilon} \eqdef H_0(U) + \log_2\frac{1}{\epsilon} \]
Approach 2: smoothing
- Note that \[ \P{\widehat{U}\neq U} \leq \bbV(P_U,\tilde{P}_U) + \sum_{u}\tilde{P}(u)\P{\widehat{U}\neq U|U=u} \]
- Pick the best $\tilde{P}_U$ close to $P_U$
- Fix $\epsilon_1,\epsilon_2>0$ such that $\epsilon=\epsilon_1+\epsilon_2$ \[ \log M = \min_{\widetilde{P}_U\in\calB^{\epsilon_1}(P_U)} \log_2\textsf{supp}(\widetilde{P}_{U}) +\log_2\frac{1}{\epsilon_2} \eqdef H_0^{\epsilon_1}(U) + \log_2\frac{1}{\epsilon_2} \]
This offers partial answers to Question 1 if we substitute $P_U\longleftarrow P_X^{\otimes n}$

Achievability - Specializing one shot lemma

Approach 3: take the limit of $n$ i.i.d. repetitions directly
- $P_U\longleftarrow P_X^{\otimes n}$
- $\gamma = n(\H{X}+\epsilon)$ for some $\epsilon>0$ so that
\[ \lim_{n\to\infty} P_e^{(n)} = 0 \qquad\textsf{(exponentially fast in $n$)} \]

There exists a sequence of fixed length $(n,M_n)$ source codes $\set{(f_n,g_n)}_{n\geq1}$ such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq \H{X} \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \]

Could we use Approach 2 directly? Yes \[ H_0^{\epsilon}(P_X^{\otimes n}) \geq n\H{X} + n\delta \qquad \text{ with } \epsilon = 2^{-\frac{n\delta^2}{2\log^2(\card{\calX}+3)}}. \]

Source coding with side information

A $(n,M_n)$ code for source coding a discrete memoryless source $p_X$ with side information $Y$ consists of:

A encoding function $f_n:\calX^n\to\set{1;M_n}$
A decoding function $g_n:\set{1;M_n}\times\calY^n\to \calX^n$

The performance of an $(n,M_n)$ code is measured in terms of
1. The rate of the code $R\eqdef \frac{\log_2 M_n}{n}$ (bits/source symbol)
2. The average probability of error
  
  \[\begin{align*} P_e^{(n)}(\calC) \eqdef \P{\widehat{X}^n\neq X^n} \eqdef \sum_{(x^n,y^n)\in\calX^n\times\calY^n}P_{XY}^{\otimes n}(x^n,y^n)\indic{g_n(f_n(x^n),y^n)\neq x^n}. \end{align*}\]

Source coding with side information

Define again \[ C_{\textsf{source}}\eqdef \inf\left\{R: \exists {(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0\right\} \]

For a discrete memoryless source $P_{XY}$, $C_{\textsf{source}} = \bbH(X|Y)$

This should be suprising: the decoder does not know $y^n$

Consider a sequence of $(n,M_n)$ codes $\set{(f_n,g_n)}_{n\geq1}$ such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \] Then $R\geq \bbH(X|Y)$.

Achievability - One Shot Lemma

The achievability uses again random binning
Consider a source $P_{UV}$, assume $P_{U|V}(u,v)>0$ for all $(u,v)$ and set $n=1$ for simplicity
Define the set \[ \calB_\gamma\eqdef\left\{(u,v)\in\calU\times\calV:\log\frac{1}{P_{U|V}(u|v)}\leq\gamma\right\}. \]
Encoding function $f:\calU\to \set{1;M}$ created by assigning an index uniformly at random in $\set{1;M}$ to each $u\in\calU$
Decoding function $g:\intseq{1}{M}\times\calV:(m,v)\mapsto u^*$, where $u^*=u$ if $u$ is the unique sequence such that $(u,v)\in\calB_\gamma$ and $f(u)=w$; otherwise, a random $u$ is declared

On average (over the random binning to create $F$), \[ \E[C]{P_e} \leq \P[P_{U}]{U\notin \calB_\gamma} + \frac{2^{\min(\gamma,\log_2\abs{\calU})}}{M}. \]